public class Test01 {
    public int maxSubArray(int[] nums) {
        int[] preSum = new int[nums.length+1];
        preSum[0] = 0;
        int max = Integer.MIN_VALUE,min = 0;
        for (int i = 1; i < nums.length + 1; i++) {
            preSum[i] = preSum[i-1] + nums[i-1];
            if(preSum[i] > max){
                max = preSum[i];
            }
            if(preSum[i] < min){
                min = preSum[i];
            }
        }

        //我们需要明确：“返回其最大和”是什么意思
        return max;
    }
    public int maxSubArray01(int[] nums) {
        // 创建前缀和数组
        int[] preSum = new int[nums.length + 1];
        preSum[0] = 0;
        int maxSum = Integer.MIN_VALUE;
        int minPreSum = 0;
        for (int i = 1; i < nums.length + 1; i++) {
            // 计算前缀和
            preSum[i] = preSum[i - 1] + nums[i - 1];
            // 更新最大子数组和
            maxSum = Math.max(maxSum, preSum[i] - minPreSum);
            // 更新前缀和的最小值
            minPreSum = Math.min(minPreSum, preSum[i]);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        Test01 test01 = new Test01();
        int res = test01.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
        System.out.println(res);
    }
}
